The present invention relates to digital systems for preparing page images for print and, more particularly, to a method and apparatus for converting one or more contone images from their native raster representation into a representation in terms of the output image raster in any desired position and angular orientation.
In the process of digitally preparing images for quality printing, there frequently occurs the general task of preparing a composite page image, consisting of text and a plurality of component images, out of a plurality of given images.
The digital representation of the final, or output, page image is normally based on a cartesian raster with a relatively high resolution, i.e. spatial-, or line- frequency--typically 1000-4000 lines per inch. In general practice, the raster is modeled as consisting of parallel lines, spaced at that spatial frequency, which lines usually correspond to the actual lines being traced by, say, a light beam when writing the image onto a plate. These parallel lines will be referred to hereunder as output raster lines, or, for short, raster lines or lines (when referring to output raster). For ease of presentation it will be assumed hereunder that the output raster lines are horizontal; it is, however, appreciated that the invention and the description applies equally well, with obvious modifications, when raster lines are in other directions. The final page image is usually represented as a sequence of short segments along each raster line, each segment being characterized by its length (so-called run-length) and by a value. The value may be either explicitly a tone value (as is usual for CT) or a reference to a table of tone values (as is usual for LW). Where the page image contains no component a blank (nonprinting) tone value is specified.
The given images are of two general types--linework (LW) and continuous-tone (CT or contone). Linework images are characterized by relatively high resolution (usually the same as the final page image) and indirect specification of tone values, while contone images have relatively low resolution (typically 300 lines per inch) and direct pixel-by-pixel specification of tone values.
It is noted that throughout the present discussion and the description of the invention the term tone value refers to any measure of darkness or lightness, such as density, of either a monochromatic image or any one color separation of a color image. It is also noted that in the context of the invention and the present discussion the digital representation of the page image (also referred to herein as the output image) is in terms of tone values and that in most systems this representation subsequently undergoes a process of screening, as is well known in the art.
The various component images are placed in the composite page image in specified positions. Quite often, linework images serve, inter alia, to define sharp boundaries of contone image components; such boundaries may be between the contone component and the background or between a contone component and the corresponding linework component or between abutting contone components.
A given (or input-) contone image is also normally based on a cartesian raster, but one that is generally modeled as a two-dimensional regular array of discrete points, at which points, usually referred to as pixels, the image is represented by tone values. The image is usually thus defined within a rectangular bounding window, whose edges are parallel to the raster's coordinate axes; the area within this window will also be referred to hereunder as the (input-) image area. As noted above, the resolution of the input image, which is the spatial frequency of its array points along one coordinate direction, is much lower than that of the output image; typically it is 200-400 lines, or pixels, per inch. Also to be noted is that when the given image, with its bounding window, is mapped into the output image, its orientation may be different, i.e. inclined at some specified angle, A (to correct for skew during scanning or to effect a rotated component in the composite image); that is, the horizontal edge of the bounding window, mapped into the output image, generally forms an angle A with respect to the horizontal axis of the output raster.
It is further noted that each input image may have a different resolution and a different angular orientation. The pixel values of each input image are stored in any convenient format, but each pixel value is always retrievable upon supplying its position within the raster's array.
The process of generating the output page image thus includes two tasks that generally require extensive computation and therefore are problematic--
(1) conversion of the contone image from its given raster representation into the output raster representation, while angularly re-orienting it, and PA0 (2) switching between, or combining, data from the given images to form the output image representation. PA0 step (a) further includes the substep of-- PA0 the retrieved values of step (b) are stored in two of the serially organized buffer memories so that values that correspond to elementary rectangles traversed by each one of the pair of master lines are stored separately in a respective one of the two buffer memories; PA0 and in step (c) the stored values are sequentially read out separately and synchronously from each of the two buffer memories to yield a stream of pairs of values, and the selecting of values that correspond to the raster line is effected by selecting from each of the pairs of values along the stream one value that corresponds to a respective one of the elementary rectangles traversed by the back-mapped raster line; that elementary rectangle is chosen by determining a sequence of directions in which the back-mapped raster line traverses the elementary rectangles and logically comparing this sequence with the sequence of directions stored in substep (iv) of step (a), to yield a choice for each elementary rectangle traversed by the raster line. PA0 each input image being represented in a first raster in terms of pixel values at pixel positions forming points in a two dimensional array, PA0 the output image being represented in a second raster in terms of values along parallel raster lines, PA0 the resolution of the output image being substantially higher than the resolution of each of the input images, PA0 the orientation of each of the component images in the second raster being at any angle A with respect to the orientation of the corresponding image in the first raster and PA0 the input images generally differing from each other in their resolution and in the orientation of their corresponding component images, PA0 the method comprising the steps of--
The first task involves overcoming the raster differences noted above, in effect orienting the contone images correctly with respect to the output raster and assigning the tonal value of each input pixel to appropriate segments of a plurality of output lines. The second task involves interleaving data (i.e., value/runlength pairs) from the various given images along each output raster line and modifying the runlength values at boundaries between output image components.
Two widely known and practiced imaging models currently serve to govern the carrying out of these tasks. One lies at the basis of the Postscript language and is specified, for example, in the Postscript Language Reference Manual, 2nd edition, by Adobe Systems Inc., Addison-Wesley Publishing Co., 1990; the other is generally adopted in so-called high-end color electronic prepress systems (CEPS), as reflected, for example, in the international standard CD-12639 for Graphic technology--Prepress digital data exchange--Tag Image File Format for Image Technology (TIFF/IT), drafts of which have been circulated by ISO-TC130/WG2.
In the Postscript model, the various image components are written in sequence into a buffer memory that eventually contains the output image in its high-resolution raster representation. The components are accumulated in such a way that where they overlap, the values of a later component in the sequence replace the values of all previously written components. A contone image may be subjected to a boundary-defining mask (also known as a clipping path) prior to being written. This is how the second of the above tasks is carried out. The first task is usually accomplished by the following method see FIG. 1!:
The given contone image area is conceptually divided into congruent rectangles 2 (usually squares), parallel to its raster grid, each rectangle assigned to one pixel and centered about its nominal position. Each output raster line to be generated is conceptually back-mapped into the coordinate system of the given contone image, oriented at an angle -A with respect to the horizontal coordinate axis (reflecting the same angular relationship within the output image, where, as noted, mapped horizontal lines are inclined at angle A), and overlaid on the grid of rectangles. A few typical lines 4 are shown in FIG. 1. All pixels over whose rectangles the back-mapped line (or portions of the back-mapped line that correspond to areas within the boundary mask) runs, are read out from the image memory in corresponding sequence and the tone value of each such pixel is assigned to the output line over a segment that corresponds to the segment that falls within that pixel's rectangle. This assignment is also gated by the data from the boundary mask. Analyzing the data flow, one realizes that if the extent of the boundary mask is large, many pixels must be read out for each output line. Moreover, for each output raster line, a different sequence of pixels must be read out, unless the orientation angle is very small (in which case a group of adjacent back-mapped raster lines may be contained within a single row of rectangles, so that the corresponding pixels need be read out only once for all the lines in that group). This is illustrated in FIG. 2, which again shows a portion of the input image overlaid by rectangles. Here, line b indicates the direction of the back-mapped output raster lines, which is at angle -A with the horizontal. Also shown are two such back-mapped raster lines 4, marked c and d, both parallel to b. The rectangles traversed by c are shown surrounded by heavy outlines 6. Line d traverses most of the same rectangles as c, avoiding a few, but also through two new rectangles, shown shaded. Thus a new sequence of pixels is required, the readout and conversion-computation of which is time consuming. Thus, the described method is disadvantageously bound by the necessity to read out and convert a new sequence of pixels for each output raster line being generated.
In the CEPS model LW components are always considered to lie on top of the CT components. Special values in the LW (so-called transparent colors) indicate areas in which an underlying CT component is to be visible; such areas in effect function as boundary masks. If there is more than one CT component, the transparent colors in the LW indicate which CT component is to be visible in each area; thus they may also serve to define boundaries between abutting CT components. A common practice is to create a pair of intermediate images, consisting of a single composite LW image and a single composite CT image. The latter is created by merging the given CT images, each such image being first rotated into its output orientation and then placed at its output position. The resolution of the composite CT remains low and the boundary between abutting components is reproduced at a low resolution version of the corresponding boundary between transparent colors in the composite LW image. This is not satisfactory for many high-quality printing applications.
According to one known improvement of the last described practice, the boundaries between abutting CT components can be defined more sharply by creating a third type of intermediate image--high-resolution contone (HRCT). The HRCT image is defined in narrow zones straddling inter-CT boundaries and represents the contone image there at LW resolution but with the whole range of CT values. The presence and use of an HRCT image obviously complicates the process and may thus be disadvantageous.
Rotation of any given CT image into the composite CT, with possible change of resolution (which is necessary when the various given images do not have the same resolution), is carried out by any of a number of methods known in the art. Typically, the positions of all pixels within the corresponding area of the composite CT are mapped back into the coordinates of the given image and their values are taken from the nearest pixel in the given image. Such a method is fast, but may give rise to distortions and artifacts. Applying interpolation produces slightly better results but requires more computations. In both cases there are obvious disadvantages.
Other models and procedures are also known in the art. They generally use methods similar to those described hereabove, in varying combinations, and thus suffer from similar disadvantages.
There is thus a widely recognized need for, and it would be highly advantageous to have, an improved method to rotate a contone image while converting it to a high resolution raster representation. There also is a need for an improved system to digitally generate composite images in output raster representation, from any given linework images and contone images. It is the goal of the present invention to provide such a method and such a system.